
# coding:utf-8

from singleLinkList import SingleLinkList


class DoubleNode(object):
    """双链表的节点类"""
    def __init__(self, value):
        self.value = value
        self.pre = None
        self.next = None


class DoubleLinkList(SingleLinkList):
    """双链表类"""
    def __init__(self, node=None):
        super().__init__()

    def is_empty(self):
        """判断链表是否为空"""
        if self.head is None:
            print("链表为空")
            return True
        else:
            return False

    def length(self):
        """输出链表长度"""
        if self.is_empty():
            print("链表为空,长度为0")
            return 0
        else:
            list_len = 1
            temp_node = self.head
            while temp_node.next is not None:
                list_len += 1
                temp_node = temp_node.next
            print("链表长度为%d" % list_len)
            return list_len

    def travel(self):
        super().travel()

    def add(self, node):
        """向链表头部添加元素"""
        if self.length() == 0:
            self.head = node
        else:
            node.next = self.head
            self.head.pre = node
            self.head = node

    def append(self, node):
        """向链表尾部添加元素"""
        if self.is_empty():
            self.head = node
        else:
            temp_node = self.head
            while temp_node.next is not None:
                temp_node = temp_node.next
            node.pre = temp_node
            temp_node.next = node

    def insert(self, pos, node):
        """向指定位置添加元素"""
        if pos <= 0:
            print("插入位置从1开始")
        elif self.length() < pos - 1:
            print("链表长度小于要插入的位置")
        elif self.length() == pos - 1:
            self.append(node)
        elif pos == 1:
            self.add(node)
        else:
            temp_node = self.head
            # 找到要插入的节点的位置
            while temp_node.next is not None and pos != 1:
                temp_node = temp_node.next
                pos -= 1
            node.pre = temp_node.pre
            temp_node.pre.next = node
            node.next = temp_node
            temp_node.pre = node

    def remove(self, node):
        """删除节点"""
        if self.is_empty():
            print("链表为空")
        else:
            index = self.search(node)
            if index:
                if index == 1:
                    if self.head.next is None:
                        self.head = None
                    else:
                        self.head = self.head.next
                        self.head.pre = None
                else:
                    temp_node = self.head
                    # 要删除的节点
                    while temp_node.next is not None and index != 1:
                        temp_node = temp_node.next
                        index -= 1
                    temp_node.pre.next = temp_node.next
                    # 判断是否为队尾元素
                    if temp_node.next is not None:
                        temp_node.next.pre = temp_node.pre
                    print("节点已删除")
            else:
                print("节点中无此元素")

    def search(self, node):
        """查找节点是否存在"""
        if self.is_empty():
            print("链表为空，要查找的元素不存在")
        else:
            temp_node = self.head
            index = 1
            if temp_node.value == node.value:
                return index
            while temp_node.next is not None and temp_node.value != node.value:
                index += 1
                temp_node = temp_node.next
            if temp_node.value == node.value:
                print("找到节点，位置为%d" % index)
                return index
            else:
                print("节点不存在")
                return 0


if __name__ == "__main__":
    n1 = DoubleNode(1)
    n2 = DoubleNode(2)
    n3 = DoubleNode(3)
    n4 = DoubleNode(4)
    n5 = DoubleNode(5)
    n6 = DoubleNode(6)

    double_list = DoubleLinkList()
    double_list.travel()
    print("----------")
    double_list.add(n1)
    double_list.add(n2)
    double_list.travel()
    print("----------")
    double_list.append(n3)
    double_list.append(n4)
    double_list.travel()
    double_list.length()
    print("----------")

    double_list.insert(1, n5)
    double_list.travel()
    print("----------")

    double_list.search(n4)
    double_list.travel()
    print("----------")

    double_list.remove(n5)
    double_list.travel()
    print("----------")
    double_list.remove(n2)
    double_list.remove(n3)
    double_list.remove(n4)
    double_list.remove(n1)
    double_list.travel()
    print("----------")












